題目：1046. Last Stone Weight

連結：https://leetcode.com/problems/last-stone-weight/description/

• 等級：Easy

class Solution {
    public int lastStoneWeight(int[] stones) {
        //max heap
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> b - a);
        for (int i = 0 ; i < stones.length;i++) heap.offer(stones[i]);
        while (heap.size() > 1)
        {
            int a = heap.poll();
            int b = heap.poll();
            heap.offer(a-b);
        }
        if (heap.isEmpty()) return 0;
        else return heap.poll();
    }
}

• Time complexity: O(n)
• Space complexity: O(1)

題目：973. K Closest Points to Origin

連結：https://leetcode.com/problems/k-closest-points-to-origin/description/

• 等級：Medium

解題思路

1. 建立一個優先權佇列並將每個點及其與原點的距離加入其中。 優先隊列在對點進行排序時會以距離作為比較的關鍵，因此距離最小的會排在隊列的前面。
2. 建立一個名為 res 的空二維數組，包含 k 行。 該數組將保存 k 個最近的點。
3. 當k大於0時，使用poll()方法從優先權佇列中刪除距離最小的點。 該點將會被加入到 res 數組的索引 k-1 處。
4. 減少 k。
5. 返回res數組。

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);

        for(int i = 0; i < points.length; i++){
            int sum = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            pq.add(new int[] {i,sum});
        }

        int[][] res = new int[k][];
        while(k > 0){
            res[k-1] = points[pq.poll()[0]];
            k--;
        }
        return res;
    }

• Time complexity: O(n)
• Space complexity: O(1)